package first.niuke.midding;

import java.util.ArrayList;
import java.util.Collections;

/**
 * @ClassName NC37
 * @description:
 * @author: 荣燊
 * @create: 2021-06-20 21:15
 **/
public class NC37 {
    public static void main(String[] args) {

    }

    // 合并区间,且保证合并后的区间按区间起点升序排列
    public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
        ArrayList<Interval> intervals1 = new ArrayList<>();
        // 区间按照起点进行排序
        Collections.sort(intervals, (a,b)->a.start-b.start);
        int i = 0;
        int len = intervals.size();
        while (i < len) {
            //
            int left = intervals.get(i).start;
            int right = intervals.get(i).end;
            while (i<len-1 && intervals.get(i+1).start <= right) {
                // 比较两区间的最大值
                right = Math.max(right, intervals.get(i+1).end);
                i++;
            }
            intervals1.add(new Interval(left, right));
            i++;
        }
        return intervals1;
    }

    public class Interval {
      int start;
      int end;
      Interval() { start = 0; end = 0; }
      Interval(int s, int e) { start = s; end = e; }
  }
}
